To solve a problem by dynamic programming instead of recursions, the key approach is to store the results of computations for the subproblems so that we only have to compute each different subproblem once. Those solutions can be stored in an array or a hash table.
Word stemming is to eliminate the commonly used words from the original documents.
For the recurrence equation , if for some constant , then .
While accessing a term, hashing is faster than search trees.
All of the Zig, Zig-zig, and Zig-zag rotations not only move the accessed node to the root, but also roughly half the depth of most nodes on the path.
In the 4-queens problem, (, , , ) correspond to the 4 queens' column indices. During backtracking, (1, 4, 2, ?) will be checked before (1, 3, 4, ?), and none of them has any solution in their branches.
In a B+ tree, leaves and nonleaf nodes have some key values in common.
In a red-black tree, an internal red node cannot be a node of degree 1.
With the same operations, the resulting skew heap is always more balanced than the leftist heap.
Insert { 1, 2, 5, 3, 8, 4, -1, 10, 128, 34, 15, 63, 18, -24, 186 } into an initially empty binomial queue, the resulting roots are 186, -24, 15 and -1.
For one operation, if its amortized time bound is , then its worst-case time bound must be .
Among the following groups of concepts, which group is not totally relevant to a search engine?
When solving a problem with input size by divide and conquer, if at each step, the problem is divided into 9 sub-problems and each size of these sub-problems is , and they are conquered in . Which one of the following is the closest to the overall time complexity?
A B+ tree of order 3 with 21 numbers has at least __ nodes of degree 2.
Delete the minimum number from the given leftist heap. Which one of the following statements is TRUE?
Insert { 9, 8, 7, 2, 3, 5, 6, 4} into an initially empty AVL tree. Which one of the following statements is FALSE?
For the result of accessing the keys 4 and 8 in order in the splay tree given in the figure, which one of the following statements is FALSE?
The function BinQueue_Merge is to merge two binomial queues H1 and H2, and return H1 as the resulting queue.
BinQueue BinQueue_Merge( BinQueue H1, BinQueue H2 )
{ BinTree T1, T2, Carry = NULL;
int i, j;
H1->CurrentSize += H2-> CurrentSize;
for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i];
switch( 4*!!Carry + 2*!!T2 + !!T1 ) {
case 0:
case 1: break;
case 2: (5分); break;
case 4: H1->TheTrees[i] = Carry; Carry = NULL; break;
case 3: Carry = CombineTrees( T1, T2 );
H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
case 5: Carry = CombineTrees( T1, Carry );
H1->TheTrees[i] = NULL; break;
case 6: Carry = CombineTrees( T2, Carry );
H2->TheTrees[i] = NULL; break;
case 7: H1->TheTrees[i] = Carry;
(5分);
H2->TheTrees[i] = NULL; break;
} /* end switch */
} /* end for-loop */
return H1;
}
| 序号 | 结果 | 得分 |
|---|---|---|
| 0 | 答案正确 | 5 |
| 1 | 答案正确 | 5 |
The function LR_Rotation is to do left-right rotation to the trouble-finder tree node T in an AVL tree.
typedef struct TNode *Tree;
struct TNode {
int key, h;
Tree left, right;
};
Tree LR_Rotation( Tree T )
{
Tree K1, K2;
K1 = T->left;
K2 = K1->right;
K1->right = (5分);
T->left = (5分);
K2->right = T;
(5分);
/* Update the heights */
K1->h = maxh(Height(K1->left), Height(K1->right)) + 1;
T->h = maxh(Height(T->left), Height(T->right)) + 1;
K2->h = maxh(K1->h, T->h) + 1;
return K2;
}
| 序号 | 结果 | 得分 |
|---|---|---|
| 0 | 答案正确 | 5 |
| 1 | 答案正确 | 5 |
| 2 | 编译错误 | 0 |